package com.zdp.leetcodeMiddle;


import com.zdp.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/*
* 题目描述：
* 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例:
输入: [1,2,3,null,5,null,4]
输出: [1, 3, 4]
解释:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-right-side-view
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 二叉树的右视图_199 {
    /*
    * 解题思路： 本质上 还是一个 层序遍历
    *  只是每次 只拿 每一层的 最右边的数据
    * */
    public List<Integer> rightSideView(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        queue.add(root);
        while(!queue.isEmpty()){
            int length = queue.size();
            for(int i=0;i<length;i++){
                TreeNode t = queue.pollFirst();
                if(i == 0){
                    result.add(t.val);
                }
                // 其余的话，不用加入
                if(t.right != null){
                    queue.add(t.right);
                }
                if(t.left != null){
                    queue.add(t.left);
                }
            }
        }
        return result;
    }
}
